import org.junit.Test;

public class MyTest{
    @Test
    public void test1(){
        int[] arr={1,2,3,4,5,6};
        sort(arr, 0, arr.length-1);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
    private void sort(int[] arr,int left,int right){
        if(left>=right) return;
        int mid=(left+right)>>1;
        //分
        sort(arr, left, mid);
        sort(arr, mid+1, right);
        //治
        merge(arr, left, right);
    }
    private void merge(int[] arr,int left,int right){
        int mid=(left+right)>>1;
        int length=right-left+1;
        int[] newArr=new int[length];
        int i=left;
        int j=mid+1;
        int idx=0;
        while(i<=mid&&j<=right){
            if(arr[i]>arr[j]){
                newArr[idx]=arr[i];
                i++;
            }else{
                newArr[idx]=arr[j];
                j++;
            }
            idx++;
        }
        if(i<=mid){
            for(;idx<length;idx++){
                newArr[idx]=arr[i];
                i++;
            }
        }else{
            for(;idx<length;idx++){
                newArr[idx]=arr[j];
                j++;
            }
        }
        for(int k:newArr){
            arr[left]=k;
            left++;
        }
    }



    @Test
    public void test2(){
        int[] stones={2,7,4,1,8,1};
        System.out.println(lastStoneWeightII(stones));

    }
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int stone:stones){
            sum+=stone;
        }
        boolean[][] dp=new boolean[stones.length+1][(sum>>1)+1];
        for(int i=0;i<dp.length;i++){
            dp[i][0]=true;
        }
        for(int i=1;i<dp[0].length;i++){
            dp[0][i]=false;
        }
        for(int j=1;j<dp[0].length;j++){
            for(int i=1;i<dp.length;i++){
                if(stones[i-1]>j){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-stones[i-1]];
                }
            }
        }
        for(int i=dp[0].length-1;i>=0;i--){
            if(dp[dp.length-1][i]) return sum-(i<<1);
        }
        return 0;
    }

    @Test
    public void test3(){
        int[] baseCosts={2,3};
        int[] toppingCosts={4,5,100};
        int target=18;
        System.out.print(closestCost(baseCosts, toppingCosts, target));
    }
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        int result=0;
        for(int i:baseCosts){
            int bo=(int) Math.pow(toppingCosts.length+1, 3)-1;
            while(bo>=0){
                int bo2=bo;
                int sum=0;
                for(int j=0;j<toppingCosts.length;j++){
                    sum+=(bo2%3)*toppingCosts[j];
                    bo2/=3;
                }
                sum+=i;
                if(Math.abs(sum-target)<Math.abs(result-target)){
                    result=sum;
                }else if(Math.abs(sum-target)==Math.abs(result-target)&&sum<result){
                    result=sum;
                }
                bo--;
            }
        }
        return result;
    }

}